// kmp
// 求模式串中最长相等前后缀，next数组
// 当模式串不匹配时，需要找到前一位的最长相等前后缀的位置继续匹配（不匹配位置的前一位的next数组的值就是该位置）

function getNext(needle) {
    let next = new Array(needle.length).fill(0)
    let left = 0 // 最长相等前后缀的长度，或前缀末尾
    let right = 1 // 后缀末尾
    while (right < needle.length) {
        // 如果前缀和后缀位置的值不相等，需要跳到当前最长相等前后缀
        while (left > 0 && needle[left] !== needle[right]) {
            left = next[left - 1]
        }
        // 如果前缀和后缀位置的值相等
        if (needle[left] === needle[right]) {
            left++
        }
        next[right] = left
        right++
    }
    return next
}

function strStr(haystack, needle) {
    if (!needle) {
        return 0
    }
    let next = getNext(needle)
    let j = 0
    for (let i = 0; i < haystack.length; i++) {
        while (j > 0 && haystack[i] !== needle[j]) {
            j = next[j - 1]
        }
        if (needle[j] === haystack[i]) {
            j++
        }
        if (j === needle.length) {
            return (i - needle.length + 1)
        }
    }
}

console.log(strStr('aabaabaafa', 'aabaaf'))